Wenbo XU Yupeng CUI Yun TIAN Siye WANG Jiaru LIN
This paper considers the recovery problem of distributed compressed sensing (DCS), where J (J≥2) signals all have sparse common component and sparse innovation components. The decoder attempts to jointly recover each component based on {Mj} random noisy measurements (j=1,…,J) with the prior information on the support probabilities, i.e., the probabilities that the entries in each component are nonzero. We give both the sufficient and necessary conditions on the total number of measurements $sum olimits_{j = 1}^J M_j$ that is needed to recover the support set of each component perfectly. The results show that when the number of signal J increases, the required average number of measurements $sum olimits_{j = 1}^J M_j/J$ decreases. Furthermore, we propose an extension of one existing algorithm for DCS to exploit the prior information, and simulations verify its improved performance.
Naoki NOGAMI Akira HIRABAYASHI Takashi IJIRI Jeremy WHITE
In this paper, we propose an algorithm that enhances the number of pixels for high-speed imaging. High-speed cameras have a principle problem that the number of pixels reduces when the number of frames per second (fps) increases. To enhance the number of pixels, we suppose an optical structure that block-randomly selects some percent of pixels in an image. Then, we need to reconstruct the entire image. For this, a state-of-the-art method takes three-dimensional reconstruction strategy, which requires a heavy computational cost in terms of time. To reduce the cost, the proposed method reconstructs the entire image frame-by-frame using a new cost function exploiting two types of sparsity. One is within each frame and the other is induced from the similarity between adjacent frames. The latter further means not only in the image domain, but also in a sparsifying transformed domain. Since the cost function we define is convex, we can find the optimal solution using a convex optimization technique with small computational cost. We conducted simulations using grayscale image sequences. The results show that the proposed method produces a sequence, mostly the same quality as the state-of-the-art method, with dramatically less computational time.
Xiaopeng LIU Xihong CHEN Lunsheng XUE Zedong XIE
In this paper, we investigate a novel preamble channel estimation (CE) method based on the compressed sensing (CS) theory in the orthogonal frequency division multiplexing system with offset quadrature amplitude modulation (OQAM/OFDM) over a frequency selective fading channel. Most of the preamble based CE methods waste power by deploying the pilots in all the subcarriers. Inspired by the CS theory, we focus on using many fewer pilots than one of traditional CE methods and realize accurate reconstruction of the channel response. After describing and analyzing the concept of OQAM/OFDM and its traditional CE methods, we propose a novel channel estimation method based on CS that requires fewer pilots in the preamble, and we design the corresponding preamble pattern to meet the requirements of CS. Simulation results validate the efficiency and superior performance of the proposed method in wireless channel.
Wenbo XU Yifan WANG Yibing GAI Siye WANG Jiaru LIN
The theory of compressed sensing (CS) is very attractive in that it makes it possible to reconstruct sparse signals with sub-Nyquist sampling rates. Considering that CS can be regarded as a joint source-channel code, it has been recently applied in communication systems and shown great potential. This paper studies compressed cooperation in an amplify-and-forward (CC-AF) relay channel. By discussing whether the source transmits the same messages in two phases, and the different cases of the measurement matrices used at the source and the relay, four decoding strategies are proposed and their transmission rates are analyzed theoretically. With the derived rates, we show by numerical simulations that CC-AF outperforms the direct compressed transmission without relay. In addition, the performance of CC-AF and the existing compressed cooperation with decode-and-forward relay is also compared.
Hiraku OKADA Shuhei SUZAKI Tatsuya KATO Kentaro KOBAYASHI Masaaki KATAYAMA
We proposed to apply compressed sensing to realize information sharing of link quality for wireless mesh networks (WMNs) with grid topology. In this paper, we extend the link quality sharing method to be applied for WMNs with arbitrary topology. For arbitrary topology WMNs, we introduce a link quality matrix and a matrix formula for compressed sensing. By employing a diffusion wavelets basis, the link quality matrix is converted to its sparse equivalent. Based on the sparse matrix, information sharing is achieved by compressed sensing. In addition, we propose compressed transmission for arbitrary topology WMNs, in which only the compressed link quality information is transmitted. Experiments and simulations clarify that the proposed methods can reduce the amount of data transmitted for information sharing and maintain the quality of the shared information.
Liping XIAO Zhibo LIANG Kai LIU
Mutipath matching pursuit (MMP) is a new reconstruction algorithm based on compressed sensing (CS). In this letter, we applied the MMP algorithm to channel estimation in orthogonal frequency division multiplexing (OFDM) communication systems, and then proposed an improved MMP algorithm. The improved method adjusted the number of children generated by candidates. It can greatly reduce the complexity. The simulation results demonstrate that the improved method can reduce the running time under the premise of guaranteeing the performance of channel estimation.
Measurement matrix construction is critically important to signal sampling and reconstruction for compressed sensing. From a practical point of view, deterministic construction of the measurement matrix is better than random construction. In this paper, we propose a novel deterministic method to construct a measurement matrix for compressed sensing, CS-FF (compressed sensing-finite field) algorithm. For this proposed algorithm, the constructed measurement matrix is from the finite field Quasi-cyclic Low Density Parity Check (QC-LDPC) code and thus it has quasi-cyclic structure. Furthermore, we construct three groups of measurement matrices. The first group matrices are the proposed matrix and other matrices including deterministic construction matrices and random construction matrices. The other two group matrices are both constructed by our method. We compare the recovery performance of these matrices. Simulation results demonstrate that the recovery performance of our matrix is superior to that of the other matrices. In addition, simulation results show that the compression ratio is an important parameter to analyse and predict the recovery performance of the proposed measurement matrix. Moreover, these matrices have less storage requirement than that of a random one, and they achieve a better trade-off between complexity and performance. Therefore, from practical perspective, the proposed scheme is hardware friendly and easily implemented, and it is suitable to compressed sensing for its quasi-cyclic structure and good recovery performance.
We consider the problem of sparse signal recovery from 1-bit measurements. Due to the noise present in the acquisition and transmission process, some quantized bits may be flipped to their opposite states. These sign flips may result in severe performance degradation. In this study, a novel algorithm, termed HISTORY, is proposed. It consists of Hamming support detection and coefficients recovery. The HISTORY algorithm has high recovery accuracy and is robust to strong measurement noise. Numerical results are provided to demonstrate the effectiveness and superiority of the proposed algorithm.
Weijun ZENG Huali WANG Xiaofu WU Hui TIAN
In this paper, we propose a compressed sensing scheme using sparse-graph codes and peeling decoder (SGPD). By using a mix method for construction of sensing matrices proposed by Pawar and Ramchandran, it generates local sensing matrices and implements sensing and signal recovery in an adaptive manner. Then, we show how to optimize the construction of local sensing matrices using the theory of sparse-graph codes. Like the existing compressed sensing schemes based on sparse-graph codes with “good” degree profile, SGPD requires only O(k) measurements to recover a k-sparse signal of dimension n in the noiseless setting. In the presence of noise, SGPD performs better than the existing compressed sensing schemes based on sparse-graph codes, still with a similar implementation cost. Furthermore, the average variable node degree for sensing matrices is empirically minimized for SGPD among various existing CS schemes, which can reduce the sensing computational complexity.
Wentao LV Jiliang LIU Xiaomin BAO Xiaocheng YANG Long WU
The classification of warheads and decoys is a core technology in the defense of the ballistic missile. Usually, a high range resolution is favorable for the development of the classification algorithm, which requires a high sampling rate in fast time, and thus leads to a heavy computation burden for data processing. In this paper, a novel method based on compressed sensing (CS) is presented to improve the range resolution of the target with low computational complexity. First, a tool for electromagnetic calculation, such as CST Microwave Studio, is used to simulate the frequency response of the electromagnetic scattering of the target. Second, the range-resolved signal of the target is acquired by further processing. Third, a greedy algorithm is applied to this signal. By the iterative search of the maximum value from the signal rather than the calculation of the inner product for raw echo, the scattering coefficients of the target can be reconstructed efficiently. A series of experimental results demonstrates the effectiveness of our method.
Xunchao CONG Guan GUI Keyu LONG Jiangbo LIU Longfei TAN Xiao LI Qun WAN
Synthetic aperture radar (SAR) imagery is significantly deteriorated by the random phase noises which are generated by the frequency jitter of the transmit signal and atmospheric turbulence. In this paper, we recast the SAR imaging problem via the phase-corrupted data as for a special case of quadratic compressed sensing (QCS). Although the quadratic measurement model has potential to mitigate the effects of the phase noises, it also leads to a nonconvex and quartic optimization problem. In order to overcome these challenges and increase reconstruction robustness to the phase noises, we proposed a QCS-based SAR imaging algorithm by greedy local search to exploit the spatial sparsity of scatterers. Our proposed imaging algorithm can not only avoid the process of precise random phase noise estimation but also acquire a sparse representation of the SAR target with high accuracy from the phase-corrupted data. Experiments are conducted by the synthetic scene and the moving and stationary target recognition Sandia laboratories implementation of cylinders (MSTAR SLICY) target. Simulation results are provided to demonstrate the effectiveness and robustness of our proposed SAR imaging algorithm.
Cuiling FAN Rong LUO Xiaoni DU
Codebooks with good parameters are preferred in many practical applications, such as direct spread CDMA communications and compressed sensing. In this letter, an upper bound on the set size of a codebook is introduced by modifying the Levenstein bound on the maximum amplitudes of such a codebook. Based on an estimate of a class of character sums over a finite field by Katz, a family of codebooks nearly meeting the modified bound is proposed.
Because accurate position information plays an important role in wireless sensor networks (WSNs), target localization has attracted considerable attention in recent years. In this paper, based on target spatial domain discretion, the target localization problem is formulated as a sparsity-seeking problem that can be solved by the compressed sensing (CS) technique. To satisfy the robust recovery condition called restricted isometry property (RIP) for CS theory requirement, an orthogonalization preprocessing method named LU (lower triangular matrix, unitary matrix) decomposition is utilized to ensure the observation matrix obeys the RIP. In addition, from the viewpoint of the positioning systems, taking advantage of the joint posterior distribution of model parameters that approximate the sparse prior knowledge of target, the sparse Bayesian learning (SBL) approach is utilized to improve the positioning performance. Simulation results illustrate that the proposed algorithm has higher positioning accuracy in multi-target scenarios than existing algorithms.
Honggyu JUNG Thu L. N. NGUYEN Yoan SHIN
We propose a cooperative spectrum sensing scheme based on sub-Nyquist sampling in cognitive radios. Our main purpose is to understand the uncertainty caused by sub-Nyquist sampling and to present a sensing scheme that operates at low sampling rates. In order to alleviate the aliasing effect of sub-Nyquist sampling, we utilize cooperation among secondary users and the sparsity order of channel occupancy. The simulation results show that the proposed scheme can achieve reasonable sensing performance even at low sampling rates.
Hui WANG Sabine VAN HUFFEL Guan GUI Qun WAN
This paper studies the problem of recovering an arbitrarily distributed sparse matrix from its one-bit (1-bit) compressive measurements. We propose a matrix sketching based binary method iterative hard thresholding (MSBIHT) algorithm by combining the two dimensional version of BIHT (2DBIHT) and the matrix sketching method, to solve the sparse matrix recovery problem in matrix form. In contrast to traditional one-dimensional BIHT (BIHT), the proposed algorithm can reduce computational complexity. Besides, the MSBIHT can also improve the recovery performance comparing to the 2DBIHT method. A brief theoretical analysis and numerical experiments show the proposed algorithm outperforms traditional ones.
Weichao SUN Zhitao HUANG Fenghua WANG Xiang WANG Shaoyi XIE
A major challenge in wideband spectrum sensing, in cognitive radio system for example, is the requirement of a high sampling rate which may exceed today's best analog-to-digital converters (ADCs) front-end bandwidths. Compressive sampling is an attractive way to reduce the sampling rate. The modulated wideband converter (MWC) proposed recently is one of the most successful compressive sampling hardware architectures, but it has high hardware complexity owing to its parallel channels structure. In this paper, we design a single channel sub-Nyquist sampling scheme to bring substantial savings in terms of not only sampling rate but also hardware complexity, and we also present a wideband power spectrum sensing and reconstruction method for bandlimited wide-sense stationary (WSS) signals. The total sampling rate is only one channel rate of the MWC's. We evaluate the performance of the sensing model by computing the probability of detecting signal occupancy in terms of the signal-to-noise ratio (SNR) and other practical parameters. Simulation results underline the promising performance of proposed approach.
Yongjie LUO Qun WAN Guan GUI Fumiyuki ADACHI
This paper proposes a novel matching pursuit generalized approximate message passing (MPGAMP) algorithm which explores the support of sparse representation coefficients step by step, and estimates the mean and variance of non-zero elements at each step based on a generalized-approximate-message-passing-like scheme. In contrast to the classic message passing based algorithms and matching pursuit based algorithms, our proposed algorithm saves a lot of intermediate process memory, and does not calculate the inverse matrix. Numerical experiments show that MPGAMP algorithm can recover a sparse signal from compressed sensing measurements very well, and maintain good performance even for non-zero mean projection matrix and strong correlated projection matrix.
Akira HIRABAYASHI Norihito INAMURO Aiko NISHIYAMA Kazushi MIMURA
We propose a novel algorithm for the recovery of non-sparse, but compressible signals from linear undersampled measurements. The algorithm proposed in this paper consists of two steps. The first step recovers the signal by the l1-norm minimization. Then, the second step decomposes the l1 reconstruction into major and minor components. By using the major components, measurements for the minor components of the target signal are estimated. The minor components are further estimated using the estimated measurements exploiting a maximum a posterior (MAP) estimation, which leads to a ridge regression with the regularization parameter determined using the error bound for the estimated measurements. After a slight modification to the major components, the final estimate is obtained by combining the two estimates. Computational cost of the proposed algorithm is mostly the same as the l1-nom minimization. Simulation results for one-dimensional computer generated signals show that the proposed algorithm gives 11.8% better results on average than the l1-norm minimization and the lasso estimator. Simulations using standard images also show that the proposed algorithm outperforms those conventional methods.
Yizhong LIU Tian SONG Yiqi ZHUANG Takashi SHIMAMOTO Xiang LI
This paper proposes a novel greedy algorithm, called Creditability-Estimation based Matching Pursuit (CEMP), for the compressed sensing signal recovery. As proved in the algorithm of Stagewise Orthogonal Matching Pursuit (StOMP), two Gaussian distributions are followed by the matched filter coefficients corresponding to and without corresponding to the actual support set of the original sparse signal, respectively. Therefore, the selection for each support point is interpreted as a process of hypothesis testing, and the preliminarily selected support set is supposed to consist of rejected atoms. A hard threshold, which is controlled by an input parameter, is used to implement the rejection. Because the Type I error may happen during the hypothesis testing, not all the rejected atoms are creditable to be the true support points. The creditability of each preliminarily selected support point is evaluated by a well-designed built-in mechanism, and the several most creditable ones are adaptively selected into the final support set without being controlled by any extra external parameters. Moreover, the proposed CEMP does not necessitate the sparsity level to be a priori control parameter in operation. In order to verify the performance of the proposed algorithm, Gaussian and Pulse Amplitude Modulation sparse signals are measured in the noiseless and noisy cases, and the experiments of the compressed sensing signal recoveries by several greedy algorithms including CEMP are implemented. The simulation results show the proposed CEMP can achieve the best performances of the recovery accuracy and robustness as a whole. Besides, the experiment of the compressed sensing image recovery shows that CEMP can recover the image with the highest Peak Signal to Noise Ratio (PSNR) and the best visual quality.
Masaki TAKANASHI Satoshi MAKIDO
Providing images captured by an on-board camera to surrounding vehicles is an effective method to achieve smooth road traffic and to avoid traffic accidents. We consider providing images using WiFi technology based on the IEEE802.11p standard for vehicle-to-vehicle (V2V) communication media. We want to compress images to suppress communication traffic, because the communication capacity of the V2V system is strictly limited. However, there are difficulties in image compression and transmission using wireless communication especially in a vehicular broadcast environment, due to transmission errors caused by fading, packet collision, etc. In this letter, we propose an image transmission technique based on compressed sensing. Through computer simulations, we show that our proposed technique can achieve stable image reconstruction despite frequent packet error.